package com.hws.leetcode.Day_01_12;

/**
 * ClassName:leetcode_300
 * Package:com.hws.leetcode.Day_01_12
 * Description:
 *
 * @ date:2022/1/12 21:12
 * @ author:hws
 */
public class leetcode_300 {

    public int lengthOfLIS(int[] nums){
        int[] dp = new int[nums.length];
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            int poker = nums[i];
            int left = 0;
            int right = piles;
            while (left < right){
                int mid = left + (right - left) / 2;
                if (dp[mid] > poker){
                    right = mid;
                }else if (dp[mid] == poker){
                    right = mid;
                }else if (dp[mid] < poker){
                    left = mid + 1;
                }
            }
            if (left == piles){
                piles++;
            }
            dp[left] = poker;
        }
        return piles;
    }

    public static void main(String[] args) {

    }

}
